package targetToOffer.thrDay;

import java.util.Arrays;

/**
 * @author Godc
 * @description 53
 */
public class Search {
    public static void main(String[] args) {
        SearchSolution searchSolution = new SearchSolution();
        int[] ints = {5,7,7,8,8,10};
        int search = searchSolution.search2(ints, 8);
        System.out.println(search);
    }
}
class SearchSolution {
    /**
     * 二分查找,在有序数组中查找目标数字
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if(nums.length == 0)
            return 0;
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        int res = 0;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target){
                int i = mid;
                while(i>=0&&nums[i]==nums[mid]){
                    res++;
                    i--;
                }
                i = mid+1;
                while(i<nums.length&&nums[i]==nums[mid]){
                    res++;
                    i++;
                }
                break;
            }
            if(nums[mid]<target)
                left = mid+1;
            if(nums[mid]>target)
                right = mid-1;
        }
        return res;
    }

    /**
     * 继续优化，可以使用两次二分来查找左右边界
     */
    public int search2(int[] nums, int target){
        if(nums.length == 0)
            return 0;
        return findIndex(nums,target) - findIndex(nums,target-1);
    }

    /**
     * 找的是最右边界
     * @param nums
     * @param target
     * @return
     */
    public int findIndex(int[] nums, int target){
        int left = 0,right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]<=target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
}